package acm.pta14;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Test {
    public static void main(String[] args) {
// 创建一个二叉树
        Tree root = new Tree(1);
        root.left = new Tree(2);
        root.right = new Tree(3);
        root.left.left = new Tree(4);
        root.right.right = new Tree(5);

        // 测试 levelOrder 方法
        List[] levelOrderResult = levelOrder(root);
        System.out.println("levelOrder method result:");
        for (List list : levelOrderResult) {
            System.out.println(list);
        }

        // 测试 levelOrder2 方法
        List[] levelOrder2Result = levelOrder2(root);
        System.out.println("levelOrder2 method result:");
        for (List list : levelOrder2Result) {
            System.out.println(list);
        }
    }

    static class Tree {
        int val;
        Tree left;
        Tree right;

        public Tree(int val) {
            this.val = val;
        }

        public Tree(int val, Tree left, Tree right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public static List[] levelOrder(Tree root) {
        Queue<Tree> queue = new LinkedList<>();
        LinkedList<Integer> left = new LinkedList<>();
        LinkedList<Integer> right = new LinkedList<>();
        Tree curEnd = root;
        Tree nextEnd = root;
        queue.add(root);
        left.add(root.val);
        while (!queue.isEmpty()) {
            Tree cur = queue.poll();
            if (cur.left != null) {
                queue.add(cur.left);
                nextEnd = cur.left;
            }
            if (cur.right != null) {
                queue.add(cur.right);
                nextEnd = cur.right;
            }
            if (cur == curEnd) {      //抵达当前边界
                right.add(cur.val);
                if (!queue.isEmpty()) left.add(queue.peek().val);
                curEnd = nextEnd;
            }
        }
        return new List[]{left, right};
    }

    public static List[] levelOrder2(Tree root) {
        Queue<Tree> queue = new LinkedList<>();
        LinkedList<Integer> left = new LinkedList<>();
        LinkedList<Integer> right = new LinkedList<>();
        Tree curEnd = root;
        Tree nextEnd = root;
        queue.add(root);
        while (!queue.isEmpty()) {
            Tree cur = queue.poll();
            if (curEnd==nextEnd){   //如果不是完全二叉树，这里会出错
                left.add(cur.val);
            }
            if (cur.left != null) {
                queue.add(cur.left);
                nextEnd = cur.left;
            }
            if (cur.right != null) {
                queue.add(cur.right);
                nextEnd = cur.right;
            }
            if (cur == curEnd) {      //抵达当前边界
                right.add(cur.val);
                curEnd = nextEnd;
            }
        }
        return new List[]{left, right};
    }
}
